The invention relates to communication networks, such as for parallel processing systems.
Parallel processing systems are computer systems containing large numbers of terminal nodes. The terminal nodes may be, for example, processors, memory elements, input/output servers, or other computer devices. The terminal nodes in parallel systems are commonly connected by a network of switch nodes that transfer information signals between the terminal nodes. Terminal nodes and switch nodes may be referred to collectively as network devices.
Message-passing networks typically route message packets by circuit-switching or by packet-switching. In circuit-switching, control packets create a source-to-destination message path through the network by configuring individual switches along the desired connection path or circuit. Once a circuit is configured, one or more message packets are transmitted from the source to the destination over the circuit. In contrast, for packet-switching, each message packet is self-routing. That is, each message packet contains its own routing information which controls the individual switches dynamically.
A circuit-switched network can be subclassified according to the underlying method of circuit configuration used by the control packets. If the control packets also obey circuit-switching to configure the network, the network is referred to as totally circuit-switched. In contrast, it is possible to construct a network in which control packets are packet-switched, and other message packets are circuit-switched.
Most message-passing networks have (1) message-passing activities in which the network transports messages from a source terminal node to a destination terminal node, and (2) service activities in which a service processor controls, initializes, interrogates, or otherwise services the communication network. These contrasting functions may be implemented by separate communication networks, each connecting all network devices. Alternatively, the message-passing and the service activities may be time-multiplexed in a single unified network.
The requirements of network service differ in several respects from the standard message passing activities of the communication network. A service processor is highly likely to send or receive a number of service message packets to or from one particular network device before commencing communication with a different network device. That is, there exists a high degree of temporal locality in service communications. Furthermore, after completing a communication with one particular network device, the service processor is highly likely to send or receive service message packets to a second network device which is close to the previous device in the communication network. That is, there also exists a high degree of spatial locality in service communications. Another attribute of network service is that the same information is likely to be sent to many different nodes. For example, the dynamic random access memory of every processing node of the network may be initialized with the same information.
Another respect in which servicing a network differs from standard message-passing is that typically only one message source services the entire network or a distinct portion of the network. In this case, the source (for example, a service processor) is the sole controller of network services for all or a part of the network.
In totally circuit-switched networks, a message is selectively interpreted by devices on the current circuit. Each device may contain a device identification register loaded with a unique value identifying that device. For a network containing N devices, each device identification register must therefore contain at least log.sub.2 N binary digits. Each message contains a device identification field which also contains at least log.sub.2 N binary digits. A message which is sent through the devices in a configured circuit is interpreted by a device only when the device identification field of the message is identical to the contents of the device identification register of the device, Because every device identification register contains a unique value, a maximum of one device along a circuit will act upon the message.